package bintree.leetcode;

public class Num236最近公共祖先 {
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findNode(root,p,q);
        return lca;
    }
//以root为根的节点单位出发，能否找到p或者Q，找到一个返回true
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root==null){
            return false;
        }
        //返回1 说明此时从左子树中至少找到了一个节点
        int left = findNode(root.left,p,q)?1:0;
        //右子树
        int right = findNode(root.right,p,q)?1:0;
        //当前树根就是p或者q的其中一个
        int mid = (root==p||root==q)?1:0;
        if (left+right+mid == 2){
            //此时p和q出现在以root为根的两个位置，这个root一定是lca！
            lca=root;
        }
        //大于零，说明至少找到一个节点
        return (left+right+mid)>0;
    }
}
